#ifndef __GLF_CONCURRENT_TICKETQUEUE_H_INCLUDED__
#define __GLF_CONCURRENT_TICKETQUEUE_H_INCLUDED__

#include <glf/core/atomic.h>
#include <glf/core/thread.h>

namespace glf {

//! Concurrent FIFO queue.
/** Queues are a type of container, specifically designed to operate in a FIFO context
 *  (first-in first-out), where elements are inserted into one end of the container and
 *  extracted from the other.
 *
 *  This class is implemented over and underlying single-producer / single-consumer queue.
 *  It uses a ticket idiom to synchronize the concurrent access.
 */
template<typename T, typename Q>
class TicketQueue : NonCopyable {
public:

	// Type definitions

	typedef T										ValueType;
	typedef Q										UnderlyingQueueType;
	typedef ValueType&								Reference;
	typedef const ValueType&						ConstReference;
	typedef typename UnderlyingQueueType::NodeType  NodeType;

public:

	//! Initializes the concurrent FIFO queue object.
	TicketQueue()
		: m_Queue() {
		Init();
	}

	//! Releases all resources used by the concurrent FIFO queue.
	~TicketQueue() {
	}

	//! Enqueue (add at the end of the queue) a new element.
	inline void Push(ConstReference value) {
		// This method assume that push will always succeed.
		GLF_DEBUG_ONLY(bool result =) TryPush(value);
		GLF_DEBUG_ONLY(GLF_ASSERT(result == true));
	}

	//! Enqueue (add at the end of the queue) a new element.
	/** It is up to the underlying queue to manage the assignment method.
	 *
	 *  \return true if the element was enqueued correctly, false otherwise.
	 */
	inline bool TryPush(ConstReference value) {
		// Wait for my turn.
		int ticket = m_Tail.m_Ticket++;
		if (ticket != m_Tail.m_NowServing) {
			while(m_Tail.m_NowServing != ticket) {
				Thread::Sleep(0);
			}
		}

		// Equeue.
		bool result = m_Queue.TryPush(value);

		// Next !
		++m_Tail.m_NowServing;

		// Return result !
		return result;
	}

	//! Try to dequeue (remove at the beginning of the queue) the next element.
	/** It is up to the underlying queue to manage the destruction method.
	 *
	 *  \return true if the element was dequeued correctly, false otherwise.
	 */
	inline bool TryPop(Reference value) {
		// Wait for my turn
		int ticket = m_Head.m_Ticket++;

		if (ticket != m_Head.m_NowServing) {
			while(m_Head.m_NowServing != ticket) {
				Thread::Sleep(0);
			}
		}

		// Dequeue
		bool result = m_Queue.TryPop(value);

		// Next
		++m_Head.m_NowServing;

		// Return result !
		return result;
	}

	//! Returns the number of elements in the queue.
	inline size_t Size() {
		return m_Queue.Size();
	}

	//! Returns whether the queue is empty, i.e. whether its size is 0.
	inline bool Empty() {
		return m_Queue.Empty();
	}

private:

	// Ticket structure
	struct TicketType {
		TicketType()
			: m_Ticket(0)
			, m_NowServing(0)
		{
		}
			
		Atomic32 m_Ticket;
		Atomic32 m_NowServing;
	};

	TicketType m_Head;

	// Delimiter between consumer part and producer part, so that they situated on
	// different cache lines.
	char cache_line_delimiter_1__[GLF_CACHE_LINE_SIZE];

	TicketType m_Tail;

	// Delimiter between consumer / producer part and the underlying queue, so that they
	// situated on different cache lines.
	char cache_line_delimiter_2__[GLF_CACHE_LINE_SIZE];

	UnderlyingQueueType m_Queue;

	//! Initializes the concurrent FIFO queue object.
	void Init() {
		m_Head.m_Ticket     = 0;
		m_Head.m_NowServing = 0;

		m_Tail.m_Ticket     = 0;
		m_Tail.m_NowServing = 0;
	}
};

} // namespace glf

#endif // __GLF_CONCURRENT_TICKETQUEUE_H_INCLUDED__
